home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / graphicgems4.lha / GemsIV / graph_layout / graph.C < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-06  |  26.4 KB  |  812 lines
  1. /************************************************************************
  2. **    TEST FILE FOR graph (Dynamic Layout Alg)
  3. **
  4. **    MODUL - MANIPULATION OF THE GRAPH DATA STRUCTURE
  5. **
  6. ** Author: dr. Szirmay-Kalos Laszlo (szirmay@fsz.bme.hu)
  7. **       Technical University of Budapest, Hungary
  8. *************************************************************************/
  9. #ifdef MSWINDOWS
  10. #include "fileio.hxx"
  11. #else
  12. #include "fileio.hxx"
  13. #endif
  14.  
  15. /************************************************************************/
  16. /*    NODE                                */
  17. /************************************************************************/
  18. /*-------------------    node constructor      ------------------*/
  19. /* Constructs node   object and initializes            */
  20. /* IN  : name and type (MOVEABLE or FIXED) of node        */
  21. /* OUT : -                            */
  22. /*--------------------------------------------------------------*/
  23. Node :: Node(pchar newname, TYPE ntype)
  24. {
  25.     newname[MAXNAME] = '\0';
  26.     strcpy(name,newname);
  27.     type  = ntype;
  28.     force = vector(0.0, 0.0);
  29.     pos      = vector(0.0, 0.0);
  30.     speed = vector(0.0, 0.0);
  31. }
  32.  
  33.  
  34. /************************************************************************/
  35. /*    RELATION                                */
  36. /************************************************************************/
  37. /*------------------- relation constructor    ------------------*/
  38. /* Constructs relation object and initializes            */
  39. /* IN  : name , related node, intensity,            */
  40. /*--------------------------------------------------------------*/
  41. Relation :: Relation( pchar nname, Node * np, double r )
  42. {
  43.     SetRelation( nname, r );
  44.     relation_to = np;
  45. }
  46.  
  47. /*-------------------  SetRelation     -------------------------*/
  48. /* Change the name intensity and relation of a constructed rel    */
  49. /* IN  : name, intensity                    */
  50. /*--------------------------------------------------------------*/
  51. void Relation :: SetRelation( pchar nname, double r )
  52. {
  53.     strcpy( name, nname );
  54.     intensity = r;
  55. }
  56.  
  57. /************************************************************************/
  58. /*    NODE ELEM                                */
  59. /************************************************************************/
  60. /*------------------- NodeElem     constructor  ------------------*/
  61. /* Constructs a node elem of a list object and initializes    */
  62. /* IN  : name and type (MOVEABLE or FIXED) of node        */
  63. /*--------------------------------------------------------------*/
  64. NodeElem :: NodeElem( pchar name, TYPE type )
  65.       : Node( name, type )
  66. {
  67.     next_node = NULL;
  68.     relation = NULL;
  69. }
  70.  
  71.  
  72. /************************************************************************/
  73. /*    RELATION ELEM                            */
  74. /************************************************************************/
  75. /*------------------- RelationNode constructor    ----------------*/
  76. /* Constructs relation node of a list object and initializes    */
  77. /* IN  : name , related node, intensity,               */
  78. /*--------------------------------------------------------------*/
  79. RelationElem :: RelationElem( pchar name, Node * p, double r )
  80.           : Relation( name, p, r )
  81. {
  82.     next_relation = NULL;
  83. }
  84.  
  85. /************************************************************************/
  86. /*    GRAPH = NODE - RELATION DATA                    */
  87. /*                                    */
  88. /*    The Graph data structure is a dynamic structure.            */
  89. /*                                    */
  90. /*    The nodes are placed on a singly linked list, where fix nodes    */
  91. /*    are on the beginning, and moveable nodes are on the end.        */
  92. /*    The nodes are also identified by serial numbers, the moveable    */
  93. /*    nodes are having positive while fixed nodes negative numbers.    */
  94. /*    Control pointers : currnode - points to the actual node        */
  95. /*             relatenode - other node which forms a pair    */
  96. /*                    with currnode for relation ops    */
  97. /*             start_node - the beginning of the list        */
  98. /*             last_node - the end of the list        */
  99. /*                                    */
  100. /*    The relations of a given node are stored on an other linked list    */
  101. /*    connected to the node of the given node. The relation node    */
  102. /*    contains name, type, intensity parameters and a pointer to the    */
  103. /*    related node. The relation of two node is stored on the        */
  104. /*    relation list of the node having smaller serial number!        */
  105. /*    Control pointers : currelation -points to the actual relation node*/
  106. /*             prevrelation - points to the relation just    */
  107. /*                before currelation on the actual relation    */
  108. /*                list.                    */
  109. /*                                    */
  110. /*  STRUCTURE OVERVIEW: P = Node, R = RelationNode            */
  111. /*                                    */
  112. /*  start_node                lastnode            */
  113. /*     P ---> P ---> P ---> P ---> P ---> P ---> NULL            */
  114. /*     |         ^        |       ^      ^                */
  115. /*     R ------------|        R------|      |                */
  116. /*     |            |          |                */
  117. /*    NULL            R-------------|                */
  118. /*                |                        */
  119. /*               NULL                        */
  120. /************************************************************************/
  121. /*------------------ Graph Constructor -------------------------*/
  122. /* Initializes Graph data structure                */
  123. /*--------------------------------------------------------------*/
  124. Graph :: Graph()
  125. {
  126.     start_node = NULL;
  127.     last_node  = NULL;
  128.     currnode   = NULL;
  129.     relatenode = NULL;
  130.     currelation     = NULL;
  131.     prevrelation = NULL;
  132.     nfixnode   = nmovnode = 0;
  133. }
  134.  
  135. /*------------------ RestoreNodes ----------------------------*/
  136. /* Restores the node-relation data structure from a file    */
  137. /* The file type is TEXT.                    */
  138. /* IN  : file name                        */
  139. /* SIDE EFFECT: - node-relation data structure is destroyed    */
  140. /*          then it is restored from the given file    */
  141. /*--------------------------------------------------------------*/
  142. void Graph :: RestoreNodes ( pchar file_name )
  143. {
  144.     char    s[MAXLINE + 1];
  145.     char    node_name[MAXNAME + 1];
  146.     char    rel_node_name[MAXNAME + 1];
  147.     char    relation_name[MAXNAME + 1];
  148.     double  x, y;
  149.     double  relation;
  150.     FileIO  fi ( "r" );
  151.     BOOL    first_rel;
  152.  
  153.     if ( !fi.OpenFile ( file_name ) ) app.Error("Input file does not exists");
  154. /*
  155. *    RESTORE NODES
  156. */
  157.     for ( ; ; ) {
  158. /*
  159. *    TRY TO INPUT NODE NAME
  160. */
  161.     if ( !fi.GetKeyWord ( "NAME" ) ) {
  162. /*
  163. *    FAILED -> END OF NODE LIST
  164. */
  165.         first_rel = TRUE;
  166.         break;
  167.     } else {
  168.         if ( !fi.GetOperator ( '=' ) ) app.Error( "= expected", fi.GetLineNum() );
  169.         if ( !fi.GetString(node_name,MAXNAME) ) app.Error( "Name expected", fi.GetLineNum() );
  170. /*
  171. *    TRY TO INPUT NODE POSITION
  172. */
  173.         if ( !fi.GetKeyWord("POSITION") ) {
  174. /*
  175. *    FAILED -> ASSUME NO POSITION, GENERATE RANDOMLY
  176. */
  177.         x = (OVERWINDOW_X - WALL_MARGIN * 2.0) /
  178.             (double)RAND_MAX * (double)rand() + WALL_MARGIN;
  179.         y = (OVERWINDOW_Y - WALL_MARGIN * 2.0) /
  180.             (double)RAND_MAX * (double)rand() + WALL_MARGIN;
  181.         if ( !fi.GetKeyAgain("TYPE") ) app.Error( "TYPE expected", fi.GetLineNum() );
  182.         } else {
  183.         if ( !fi.GetOperator ( '=' ) ) app.Error( "= expected", fi.GetLineNum() );
  184.         if ( !fi.GetVariable( &x, 0.0, OVERWINDOW_X ) || !fi.GetVariable( &y, 0.0, OVERWINDOW_Y ) )
  185.             app.Error( "Coordinate out of space", fi.GetLineNum() );
  186.         if ( !fi.GetKeyWord("TYPE") )  app.Error( "TYPE expected", fi.GetLineNum() );
  187.         }
  188. /*
  189. *    TRY TO INPUT TYPE PARAMETERS
  190. */
  191.         if ( !fi.GetOperator ( '=' ) ) app.Error( "= expected", fi.GetLineNum() );
  192.         if ( !fi.GetString( s, MAXLINE ) ) app.Error("Line too long", fi.GetLineNum() );
  193. /*
  194. *    ADD NEW NODE TO THE DATA STRUCTURE AND CHECK THE NAME IF UNIQUE
  195. */
  196.         if ( strcmp( s, "FIXED" ) == 0 ) {
  197.         if ( !AddNode(node_name, FIXED_NODE) )      app.Error("Not unique node name", fi.GetLineNum() );
  198.         } else if ( strcmp( s, "MOVEABLE" ) == 0 ) {
  199.         if ( !AddNode(node_name, MOVEABLE_NODE) ) app.Error("Not unique node name", fi.GetLineNum() );
  200.         } else                      app.Error("Invalid Node type", fi.GetLineNum() );
  201.  
  202.         currnode -> Position( ) = vector( x, y );
  203.     }
  204.     }
  205. /*
  206. *    RESTORE RELATIONS
  207. */
  208.     for( ; ; ) {
  209. /*
  210. *    TRY TO GET RELATION LIST HEAD, IF FAIL -> END OF INPUT
  211. */
  212.     if ( first_rel ) {
  213.         if ( !fi.GetKeyAgain ( "RELATIONS" ) )  break;
  214.         first_rel = FALSE;
  215.     } else {
  216.         if ( !fi.GetKeyWord ( "RELATIONS" ) )  break;
  217.     }
  218.     if ( !fi.GetKeyWord("OF") )  app.Error("OF expected", fi.GetLineNum() );
  219.     if ( !fi.GetString( node_name, MAXNAME ) ) app.Error("Name too long", fi.GetLineNum() );
  220.     if ( !fi.GetKeyWord ( "NODE" ) ) app.Error("NODE expected", fi.GetLineNum() );
  221. /*
  222. *    IDENTIFY NODE
  223. */
  224.     if ( !SearchNode( node_name ) ) app.Error("Not declared Node", fi.GetLineNum() );
  225. /*
  226. *    TRY TO INPUT RELATION LIST
  227. */
  228.     for( ; ; ) {        // get the whole relation list of this node
  229. /*
  230. *    TRY TO GET RELATION NAME
  231. */
  232.         if ( !fi.GetKeyWord ( "RELATION" ) ) {
  233. /*
  234. *    FAILED -> CHECK END OF RELATION MARKER
  235. */
  236.         if ( !fi.GetKeyAgain ( "END" ) ) app.Error("END expected", fi.GetLineNum() );
  237.         else break;
  238.         }
  239.         if ( !fi.GetString( relation_name, MAXNAME ) ) app.Error("Name too long", fi.GetLineNum() );
  240. /*
  241. *    CHECK IF NO-NAME RELATION
  242. */
  243.         if ( strcmp( relation_name, "*" ) == 0 ) relation_name[0] = '\0';
  244.         if ( !fi.GetOperator ( ':' ) ) app.Error(": expected", fi.GetLineNum() );
  245. /*
  246. *    TRY TO GET RELATED NODE WITH RELATION PARAMETERS
  247. */
  248.         if ( !fi.GetKeyWord("RELATED") )   app.Error("RELATED expected", fi.GetLineNum() );
  249.         if ( !fi.GetKeyWord("TO") )           app.Error("TO expected", fi.GetLineNum() );
  250.         if ( !fi.GetString( rel_node_name, MAXNAME ) ) app.Error("Name expected", fi.GetLineNum() );
  251.         if ( !fi.GetKeyWord("WITH") )      app.Error("WIDTH expected", fi.GetLineNum() );
  252.         if ( !fi.GetKeyWord("INTENSITY") ) app.Error("INTENSITY expected", fi.GetLineNum() );
  253.  
  254.         if ( !fi.GetVariable( &relation, -MAXRELATION, MAXRELATION ) )
  255.         app.Error("Relation is out of range", fi.GetLineNum() );
  256. /*
  257. *    BUILD THE NEW RELATION INTO THE DATA STRUCTURE
  258. */
  259.         NodeElem * tmpnode = currnode;
  260.         if ( !RelSearchNode( rel_node_name ) ) app.Error("Not declared Node", fi.GetLineNum() );
  261.         AddRelation( relation_name, relation );
  262.         currnode = tmpnode;
  263.     }
  264.     }
  265.  
  266.     fi.CloseFile();
  267. }
  268.  
  269. /*------------------  SaveNodes      ----------------------------*/
  270. /* Saves the node-relation data structure to a file name      */
  271. /* The file type is TEXT.                    */
  272. /* IN  : file name                        */
  273. /*--------------------------------------------------------------*/
  274. BOOL Graph :: SaveNodes ( pchar file_name )
  275. {
  276.     char s[MAXLINE];
  277.     FileIO fo ( "w" );
  278.  
  279.     if ( !fo.OpenFile (file_name) ) return FALSE;
  280. /*
  281. *    SAVE NODES
  282. */
  283.     if ( !FirstNode() ) {
  284.     fo.CloseFile( );
  285.     return TRUE;
  286.     }
  287.  
  288.     do {
  289.     sprintf(s,
  290.         "NAME = %s POSITION =  %6.3lf %6.3lf TYPE = %s\n",
  291.         currnode -> GetName(),
  292.         currnode -> Position().X(),
  293.         currnode -> Position().Y(),
  294.         (currnode -> GetType() == FIXED_NODE ? "FIXED" : "MOVEABLE"));
  295.     fo.PutString( s );
  296.     } while ( NextNode() );
  297.  
  298. /*
  299. *    SAVE RELATIONS
  300. */
  301.     FirstNode();
  302.     do {
  303.        sprintf(s,
  304.             "\nRELATIONS OF %s NODE\n",
  305.           currnode -> GetName());
  306.       fo.PutString( s );
  307.  
  308.       if ( !FirstRelation() ) {
  309.         fo.PutString( "END\n" );        // END OF RELATION MARKER
  310.           continue;
  311.       }
  312.  
  313.       do {
  314.           if ( strlen( currelation -> GetName() ) != 0 )
  315.          sprintf(s, "RELATION %s : ", currelation -> GetName() );
  316.           else
  317.          sprintf(s, "RELATION * : ");
  318.           fo.PutString( s );
  319.  
  320.           sprintf(s,
  321.               "RELATED TO %s WITH INTENSITY %6.3lf \n",
  322.               currelation -> GetOtherNode() -> GetName(),
  323.               currelation -> GetRelation() );
  324.           fo.PutString( s );
  325.       } while ( NextRelation() );
  326.  
  327.       fo.PutString( "END\n" );      // END OF RELATION MARKER
  328.  
  329.     } while ( NextNode() );
  330.  
  331.     fo.CloseFile( );
  332.     return TRUE;
  333. }
  334.  
  335.  
  336. /*-------------------      SetNodePos      --------------------*/
  337. /* Sets the position of a node                      */
  338. /* IN  : new position                        */
  339. /*--------------------------------------------------------------*/
  340. void Graph :: SetNodePos ( vector p )
  341. {
  342.     if ( currnode != NULL ) currnode -> Position( ) = p;
  343. }
  344.  
  345. /*------------------------ GetRelation     -----------------------*/
  346. /* Gets the relation intensity of the actual relation        */
  347. /* IN  : -                            */
  348. /* OUT : intensity ( -MAXRELATION -> MAXRELATION )        */
  349. /*--------------------------------------------------------------*/
  350. double Graph :: GetRelation( )
  351. {
  352.     if (currelation != NULL) return currelation -> GetRelation( );
  353.     else             return 0.0;
  354. }
  355.  
  356. /*------------------------ GetRelationName ---------------------*/
  357. /* Gets the name of the actual relation                */
  358. /* OUT : name of NULL if no relation                */
  359. /*--------------------------------------------------------------*/
  360. pchar Graph :: GetRelationName( )
  361. {
  362.     if ( currelation != NULL ) return currelation -> GetName( );
  363.     else               return NULL;
  364. }
  365.  
  366. /*------------------------   AddNode   -----------------------*/
  367. /* Checks if a node having the same name exist and if not new */
  368. /* node is allocated and added to the beginning of the list if*/
  369. /* the node is FIXED or to the end if it is MOVEABLE          */
  370. /* IN  : name and type of the new node                  */
  371. /* OUT : is this name unique ?                      */
  372. /* SIDE EFFECT: currnode is set to the new node.          */
  373. /*        if FIXED node                      */
  374. /*          start_node adjusted, nfixnode incremented   */
  375. /*        if MOVEABLE NODE                  */
  376. /*          last_node adjusted, nmovnode incremented    */
  377. /*------------------------------------------------------------*/
  378. BOOL Graph :: AddNode ( pchar name, char type )
  379. {
  380. /*
  381. *    DECIDE IF THIS NAME IS UNIQUE, IF NOT RETURN ERROR
  382. */
  383.     if ( SearchNode( name ) ) return FALSE;
  384.  
  385.     currnode = new NodeElem(name, type);
  386.  
  387.     if (start_node == NULL) {
  388. /*
  389. *    IF THIS IS THE FIRST NODE
  390. */
  391.     start_node = last_node = currnode;
  392.     } else {
  393.     if ( type == FIXED_NODE ) {
  394. /*
  395. *    IF FIXED NODE -> ADD TO THE BEGINNING OF THE LIST
  396. */
  397.         currnode -> SetNext( start_node );
  398.         start_node = currnode;
  399.     } else {
  400. /*
  401. *    IF MOVEABLE NODE -> ADD TO THE END OF THE LIST
  402. */
  403.         last_node -> SetNext( currnode );
  404.         last_node = currnode;
  405.     }
  406.     }
  407.     if ( type == FIXED_NODE ) {
  408.     nfixnode++;
  409.     currnode -> SetSerNum( -nfixnode );
  410.     } else {
  411.     nmovnode++;
  412.     currnode -> SetSerNum( nmovnode );
  413.     }
  414.     return TRUE;
  415. }
  416.  
  417. /*------------------------  SearchNode      --------------------*/
  418. /* Searches node by name                      */
  419. /* IN  : searched name                          */
  420. /* OUT : is there node having this name ?              */
  421. /* SIDE EFFECT: currnode is set to the found node.          */
  422. /*------------------------------------------------------------*/
  423. BOOL Graph :: SearchNode ( pchar name )
  424. {
  425.     if ( !FirstNode() ) return FALSE;
  426.     do {
  427.     if ( strcmp( currnode -> GetName(), name) == 0 ) return TRUE;
  428.     } while ( NextNode () );
  429.  
  430.     return FALSE;
  431. }
  432.  
  433. /*------------------------  RelSearchNode --------------------*/
  434. /* Searches relate node by name                      */
  435. /* IN  : picked position                    */
  436. /* OUT : is there node in the pick aperture ?              */
  437. /* SIDE EFFECT:                            */
  438. /*  To ensure that relatenode has greater serial number than  */
  439. /*  currnode:                              */
  440. /*     IF found node has smaller serial number than currnode*/
  441. /*          relatenode is set to currnode            */
  442. /*          currnode is set to the found node            */
  443. /*     ELSE                            */
  444. /*          relatenode is set to the found node.        */
  445. /*  Initializes currelation to the relation of currnode and   */
  446. /*  relatenode.                              */
  447. /*--------------------------------------------------------------*/
  448. BOOL Graph :: RelSearchNode ( pchar name )
  449. {
  450.     NodeElem * oldcurrnode = currnode;
  451.     BOOL       found       = SearchNode( name );
  452.  
  453.     if ( found ) {
  454.     relatenode = currnode;
  455.     currnode = oldcurrnode;
  456.     SwapRelation( );
  457.     SearchRelation( );
  458.     } else {
  459.     currelation = NULL;
  460.     currnode = oldcurrnode;
  461.     }
  462.     return found;
  463. }
  464.  
  465. /*------------------ SearchRelation ----------------------------*/
  466. /* Search for a relation between currnode and relatenode.   */
  467. /* If this relation doesnot exist currelation is NULL and    */
  468. /* prevrelation points to the end of the relation list of    */
  469. /* currnode.                              */
  470. /* IN  : -                            */
  471. /* OUT : EMPTY_LIST  - No relation list                */
  472. /*       FIRST_FOUND - The first relation node found        */
  473. /*       FOUND     - Not the first node found        */
  474. /*       NOT_FOUND     - No such relation            */
  475. /* SIDE EFFECT: currelation= searched relation or NULL        */
  476. /*        prevrelation= the previous relation or the last */
  477. /*                  node of the relation list or NULL */
  478. /*                  if no node at all            */
  479. /*--------------------------------------------------------------*/
  480. int Graph :: SearchRelation ( )
  481. {
  482.     currelation = currnode -> GetRelation( );
  483.     prevrelation = currnode -> GetRelation( );
  484.     if (currelation == NULL) return EMPTY_LIST;
  485.     if (currelation -> GetOtherNode() == relatenode) return FIRST_FOUND;
  486.  
  487.     currelation = prevrelation -> GetNext();
  488.  
  489.     for ( ; ; ) {
  490.     if (currelation == NULL)             return NOT_FOUND;
  491.     if (currelation -> GetOtherNode() == relatenode) return FOUND;
  492.     prevrelation = currelation;
  493.     currelation = prevrelation -> GetNext();
  494.     }
  495. }
  496.  
  497. /*------------------------  SwapRelation    --------------------*/
  498. /*  To ensure that relatenode has greater serial number than  */
  499. /*  currnode:                              */
  500. /*    IF relatenode node has smaller serial number than   */
  501. /*    relatenode and currnode are swapped            */
  502. /* IN  : -                            */
  503. /* OUT : -                            */
  504. /*--------------------------------------------------------------*/
  505. void Graph :: SwapRelation ( )
  506. {
  507.     NodeElem * tmpnode;
  508.  
  509.     if ( currnode == NULL || relatenode == NULL ) return;
  510.  
  511.     if ( currnode -> GetSerNum() > relatenode -> GetSerNum() ) {
  512.     tmpnode = currnode;
  513.     currnode = relatenode;
  514.     relatenode = tmpnode;
  515.     }
  516. }
  517.  
  518. /*--------------------- AddRelation ----------------------------*/
  519. /* Adds new or changes the parameters of an existing relation.    */
  520. /* If this is a new relation RelationNode is allocated and    */
  521. /* placed on the end of relation list of currnode.          */
  522. /* The parameters are set according to the explicit parameters    */
  523. /*  and the implicit relatenode par.                  */
  524. /* IN  : name,intensity, type                    */
  525. /* OUT : -                            */
  526. /* SIDE EFFECT: currelation= new or changed relation        */
  527. /*--------------------------------------------------------------*/
  528. void Graph :: AddRelation ( pchar name, double rel )
  529. {
  530. /*
  531. *    CHECK IF THIS RELATION EXISTS OR FIND THE END OF RELATION LIST
  532. */
  533.     switch ( SearchRelation( ) ) {
  534.  
  535.     case FIRST_FOUND:         //       THIS RELATION HAS BEEN ALREADY DEFINED
  536.     case FOUND :
  537.     currelation -> SetRelation( name, rel );
  538.     return;
  539.  
  540.     case NOT_FOUND:           //    NOT FIRST ADD NEW RELATION TO THE END OF LIST
  541.     currelation = new RelationElem ( name, relatenode, rel );
  542.     prevrelation -> SetNext ( currelation );
  543.     return;
  544.  
  545.     case EMPTY_LIST:        //       THIS IS GOING TO BE THE FIRST
  546.     currelation = new RelationElem ( name, relatenode, rel );
  547.     currnode -> SetRelation( currelation );
  548.     return;
  549.     }
  550. }
  551.  
  552. /*--------------------- FirstNode ----------------------------*/
  553. /* Select currnode as start_node (beginning of the list        */
  554. /* IN  : -                            */
  555. /* OUT : Are nodes on the list                      */
  556. /*--------------------------------------------------------------*/
  557. BOOL Graph :: FirstNode ( )
  558. {
  559.     if ( (currnode = start_node) == NULL ) return FALSE;
  560.     else                   return TRUE;
  561. }
  562.  
  563. /*--------------------- FirstMoveNode --------------------------*/
  564. /* Select currnode as first moveable node on the list        */
  565. /* IN  : -                            */
  566. /* OUT : Are moveable nodes on the list                  */
  567. /*--------------------------------------------------------------*/
  568. BOOL Graph :: FirstMoveNode ( )
  569. {
  570.     if ( (currnode = start_node) == NULL ) return FALSE;
  571.  
  572.     while ( currnode -> GetType() != MOVEABLE_NODE ) {
  573.     currnode = currnode -> GetNext();
  574.     if ( currnode == NULL ) return FALSE;
  575.     }
  576.     return TRUE;
  577. }
  578.  
  579. /*---------------------     NextNode ----------------------------*/
  580. /* Let currnode be the next after currnode              */
  581. /* IN  : maximal serial number to be considered of ALL_NODES  */
  582. /* OUT : Was it the last node?                      */
  583. /* SIDE EFFECT: currnode = NULL if no more nodes          */
  584. /*------------------------------------------------------------*/
  585. BOOL Graph :: NextNode ( int maxsernum )
  586. {
  587.     if ( maxsernum == ALL_NODES ) {
  588.     if (( currnode = currnode -> GetNext() ) == NULL ) return FALSE;
  589.     } else {
  590.     if (( currnode = currnode -> GetNext() ) == NULL ||
  591.           currnode -> GetSerNum() > maxsernum ) return FALSE;
  592.     }
  593.     return TRUE ;
  594. }
  595.  
  596. /*---------------------     FirstRelation    ------------------------*/
  597. /* Select currrelation as first relation of the relation list    */
  598. /* of currnode.                              */
  599. /* IN  : -                            */
  600. /* OUT : Has the currnode any relation?                  */
  601. /*--------------------------------------------------------------*/
  602. BOOL Graph :: FirstRelation ( )
  603. {
  604.     if ( (currelation = currnode -> GetRelation()) == NULL ) {
  605.     relatenode = NULL;
  606.     return FALSE;
  607.     } else {
  608.     relatenode = (NodeElem *)( currelation -> GetOtherNode() );
  609.     return TRUE;
  610.     }
  611. }
  612.  
  613. /*---------------------     NextRelation --------------------------*/
  614. /* Let currelation the next after currelation            */
  615. /* IN  : -                            */
  616. /* OUT : Was it the last relation of the list?            */
  617. /*--------------------------------------------------------------*/
  618. BOOL Graph :: NextRelation ( )
  619. {
  620.     if ( (currelation = currelation -> GetNext()) == NULL ) {
  621.     relatenode = NULL;
  622.     return FALSE;
  623.     } else {
  624.     relatenode = (NodeElem *)( currelation -> GetOtherNode() );
  625.     return TRUE;
  626.     }
  627. }
  628.  
  629. /*------------------   RandomArrange ---------------------------*/
  630. /* Random arrangement of nodes                    */
  631. /*--------------------------------------------------------------*/
  632. void Graph :: RandomArrange( )
  633. {
  634. /*
  635. *    SKIP FIXED NODES
  636. */
  637.     if ( !FirstMoveNode() ) return;
  638. /*
  639. *     MAIN CYCLE OF PLACING MOVEABLE NODES RANDOMLY
  640. */
  641.     do {
  642.     currnode -> Position( ) = vector((OVERWINDOW_X - WALL_MARGIN * 2.0) /
  643.                      (double)RAND_MAX * (double)rand() + WALL_MARGIN,
  644.                      (OVERWINDOW_Y - WALL_MARGIN * 2.0) /
  645.                      (double)RAND_MAX * (double)rand() + WALL_MARGIN );
  646.     } while ( NextNode() );
  647. }
  648.  
  649. /************************************************************************/
  650. /*  OBJECT SPACE                            */
  651. /************************************************************************/
  652. /*----------------- ObjectSpace Constructor --------------------*/
  653. /* Initializes object space window                */
  654. /* IN  : -                            */
  655. /* OUT : -                            */
  656. /*--------------------------------------------------------------*/
  657. ObjectSpace :: ObjectSpace( )
  658.     :vwindow( 0, 0, (CoOrd)OVERWINDOW_Y, (CoOrd)OVERWINDOW_X ),
  659.      viewport( 0, 0, WINDOW_WIDTH, WINDOW_HEIGHT )
  660. {
  661. }
  662.  
  663. /*------------------------ SetScale ----------------------------*/
  664. /* Initializes window -> viewport transform            */
  665. /* IN  : -                            */
  666. /* OUT : -                            */
  667. /*--------------------------------------------------------------*/
  668. void ObjectSpace :: SetScale()
  669. {
  670.     scale_x = (double)viewport.Width() / (double)vwindow.Width();
  671.     scale_y = (double)viewport.Height() / (double)vwindow.Height();
  672. }
  673.  
  674.  
  675. /*--------------------- SetViewPort ----------------------------*/
  676. /* Sets viewport (Canvas RectAngle)                */
  677. /* IN  : new viewport                        */
  678. /* OUT : -                            */
  679. /* SIDE EFFECT: Recalculates window->viewport transform        */
  680. /*--------------------------------------------------------------*/
  681. void ObjectSpace :: SetViewPort( RectAngle v )
  682. {
  683.     viewport = v;
  684.     SetScale();
  685. }
  686.  
  687.  
  688. /*--------------------- ScreenPos ------------------------------*/
  689. /* Transform a point from object space to screen space        */
  690. /* IN  : object space position                    */
  691. /* OUT : screen space coordinates of point            */
  692. /*--------------------------------------------------------------*/
  693. Point ObjectSpace :: ScreenPos( vector p )
  694. {
  695.     CoOrd x = (CoOrd)((p.X()-(double)vwindow.HorPos()) * scale_x);
  696.     CoOrd y = (CoOrd)((p.Y()-(double)vwindow.VerPos()) * scale_y);
  697.     return Point(x,y);
  698. }
  699.  
  700. /*--------------------- ScreenPos ------------------------------*/
  701. /* Gets the position of a NODE in screen coordinate system    */
  702. /* IN  : pointer to the NODE                    */
  703. /* OUT : screen space coordinates of NODE position        */
  704. /*--------------------------------------------------------------*/
  705. Point ObjectSpace :: ScreenPos( NodeElem * pnode )
  706. {
  707.     return ScreenPos( pnode -> Position() );
  708. }
  709.  
  710. /************************************************************************/
  711. /*  GRAPH WINDOW                            */
  712. /************************************************************************/
  713. /*-----------------   GraphWindow constructor ------------------*/
  714. /* Reads the input file defined in argv[1]            */
  715. /*--------------------------------------------------------------*/
  716. GraphWindow :: GraphWindow( int argc, char * argv[] )
  717.          : AppWindow( argc, argv )
  718. {
  719.     if ( argc > 1 ) {
  720.         graph.RestoreNodes( argv[1] );
  721.     } else    app.Error( "Input file missing" );
  722. }
  723.  
  724. /*------------------------   ExposeAll      ----------------------*/
  725. /* Redraw the graph on the screen                */
  726. /*--------------------------------------------------------------*/
  727. void GraphWindow :: ExposeAll( ExposeEvent * event )
  728. {
  729.     Text( "<L> = Layout Algorithm", Point(20, 20) );
  730.     Text( "<R> = Random Arrange", Point(20, 40) );
  731.     Text( "<Q> = Quit & Save", Point(20, 60) );
  732.  
  733. /*
  734. *    SET WINDOW     - VIEWPORT TRANSFORM
  735. */
  736.     if ( event ) graph.SetViewPort( Canvas() );
  737. /*
  738. *    DISPLAY RELATIONS
  739. */
  740.     graph.FirstNode();
  741.     do {
  742.     if ( graph.FirstRelation() ) {
  743.         do ShowRelation(); while ( graph.NextRelation() );
  744.     }
  745.     } while ( graph.NextNode() );
  746. /*
  747. *    DISPLAY NODES
  748. */
  749.     if ( !graph.FirstNode() ) return;
  750.     do ShowNode( ); while ( graph.NextNode() );
  751. }
  752.  
  753. /*---------------------      MouseButtonDn      ----------------------*/
  754. /* React to Mouse button down event!                */
  755. /*--------------------------------------------------------------*/
  756. void GraphWindow :: KeyPressed( KeyEvent * event )
  757. {
  758.     switch ( event -> GetASCII() ) {
  759.     case 'L':
  760.     case 'l': switch ( graph.Placement() ) {
  761.           case STOPPED: RePaint();
  762.                 break;
  763.           case INSTABLE:app.Warning("Instable system");
  764.                 break;
  765.           case TOO_LONG:app.Warning("Solution takes too long");
  766.                 break;
  767.           }
  768.           break;
  769.     case 'R':
  770.     case 'r': graph.RandomArrange();
  771.           RePaint();
  772.           break;
  773.     case 'Q':
  774.     case 'q': graph.SaveNodes( "ggg.dat" );
  775.           app.Quit();
  776.     }
  777. }
  778.  
  779. /*---------------------      ShowNode    ------------------------*/
  780. /* Shows current node as a rectangle and a text              */
  781. /*------------------------------------------------------------*/
  782. void GraphWindow :: ShowNode( )
  783. {
  784.  
  785.     DrawRectangle( RectAngle( graph.ScreenPos().X() - NODESIZE_X / 2,
  786.                   graph.ScreenPos().Y() - NODESIZE_Y / 2,
  787.                   NODESIZE_X, NODESIZE_Y) );
  788.  
  789.     Text( graph.GetNode() -> GetName(), graph.ScreenPos() );
  790. }
  791.  
  792. /*---------------------      ShowRelation      ----------------------*/
  793. /* Shows the current relation as a line and a text        */
  794. /*--------------------------------------------------------------*/
  795. void GraphWindow :: ShowRelation( )
  796. {
  797.     MoveTo( graph.ScreenPos() );
  798.     LineTo( graph.RelScreenPos() );
  799.     Text( graph.GetRelationName(),
  800.       Point( (graph.ScreenPos().X() + graph.RelScreenPos().X()) / 2,
  801.          (graph.ScreenPos().Y() + graph.RelScreenPos().Y()) / 2 ) );
  802. }
  803.  
  804. /************************************************************************/
  805. /*  WINDOW MANAGER INDEPENDENT ENTRY POINT                */
  806. /************************************************************************/
  807. void App :: Start( int argc, char * argv[] )
  808. {
  809.     GraphWindow graphwindow( argc, argv );
  810.     graphwindow.MessageLoop( );
  811. }
  812.